class HeapsortAlgorithm():
	"""
	Heapsort
	"""
	def __init__(self, lista):
		#super(Heapsort, self).__init__()
		self.lista = lista
		self.heapsort(self.lista)

	def heapsort(self,lista):
		self.build_max_heap(lista)
		size = len(lista)
		for indice in xrange((size), 0, -1):
			temp = lista[1]
			lista[1] = lista[indice]
			lista[indice] =  temp
			sze = size -1
			print 'ListaHeaps : ', lista
			self.max_heapify(lista,1)

	def max_heapify(self,lista,indice):
		l = self.left(indice)-1
		r = self.right(indice)-2
		largest = 0
		#print 'max_heapify : ', lista
		#print 'indice : ', indice
		#print 'Lista indice : ', lista[indice]

		if l <= len(lista) & lista[l] > lista[indice]:
			largest = l
		else:
			largest = indice

		if r <= len(lista) & lista[r] > lista[largest]:
			largest = r

		if largest != indice:
			temp = lista[indice]
			lista[indice] = lista[largest]
			lista[largest] = temp
			print '\n*Ma Heap L :  ', lista
			self.max_heapify(lista, largest)

	def build_max_heap(self,lista):
		size = len(lista)
		half_size = size/2
		for indice in xrange((half_size),0,-1):
			print 'BUILD L :     ', lista
			self.max_heapify(lista,indice)

	def parent(self, indice):
		return i/2

	def right(self,indice):
		return 2*indice+1

	def left(self, indice):
		return 2*indice

if __name__ == "__main__":
	lista=[16,4,10,14,7,9,3,2,8,1]
	print '** Heapsort **\nLista Inicial : ', lista
	heapsortObject = HeapsortAlgorithm(lista)
	print 'Lista Ordenada : ', lista

	